package programmercarl.动态规划.C17;

class Solution1 {
    public int findMaxForm(String[] strs, int m, int n) {
        //
        int zeroNums, oneNums;
        int dp[][] = new int[m + 1][n + 1];
        //递推公式
        //dp[i][j]=max(dp[i][j],dp[i-zeroNums][j-oneNums]+1) //滚动数组覆盖的方式
        //初始化为0即可
        for (String str : strs) {
            zeroNums = 0;
            oneNums = 0;
            for (int i = 0; i < str.length(); i++) {
                if (str.charAt(i) == '0') {
                    zeroNums++;
                } else {
                    oneNums++;
                }
            }
            for (int i = m; i >= zeroNums; i--) {
                for (int j = n; j >= oneNums; j--) {
                    dp[i][j] = Math.max(dp[i][j], dp[i - zeroNums][j - oneNums] + 1);
                }
            }
        }
        return dp[m][n];
    }
}